10811번 바구니 뒤집기

Day4 4단계 20231021
배열의 정해진 인덱스 영역 내의 요소들의 순서 바꾸기

• 내 풀이 : 범위가 정해지면 몇 번 교체할 건지 결정
  • 시작 위치에서 마지막 위치를 뺀 결과가 홀수이면 ((end-start)/2+1) 회, 짝수이면 ((end-start)/2) 회 교체를 반복한다.
    • 숫자 교체 시에는 시작 위치부터 마지막 위치의 중앙으로부터 대칭 되는 위치를 index로 사용했다.
  • end - start == 1 이면 두 위치의 숫자는 바로 옆이니까 1회 자리 바꿈 한다.

if (end - start > 1) {
	if ((end - start) % 2 == 1) {
		range = (end - start) / 2 + 1;
	} else {
		range = (end - start) / 2;
	}
	for (int j = 0; j < range; j++) {
		temp = baskets[end - j];
		baskets[end - j] = baskets[start + j];
		baskets[start + j] = temp;
} else if (end - start == 1) {
	temp = baskets[end];
	baskets[end] = baskets[start];
	baskets[start] = temp;
}

• 다른 사람의 풀이 : 범위 내의 요소들을 순차적으로 교체
  • 시작 위치부터 마지막 위치까지 범위를 줄여가면서 배열 요소를 1 개씩 오른쪽으로 이동시킨다.
  • 1번 위치부터 4번 위치까지 역순 정렬이라고 한다면
    • 처음 1번 위치의 숫자를 4번 위치에 올 때까지 그 사이의 요소들과 자리바꿈
    • 4번 위치에 숫자는 이동 시킬 필요가 없으므로 이제 1번 위치부터 3번 위치까지 범위
    • 줄어든 범위에서의 1번 위치를 3번 위치까지 이동(원본의 2번 위치 숫자가 원본 마지막 위치인 4번 위치의 바로 왼쪽인 3번 위치로 이동한다)
    • 다음은 1번 위치와 2번 위치 범위에서 서로 교환(원본 4번 위치 숫자가 1번 위치에, 원본 3번 위치 숫자가 2번에 온다)
    • 역순 정렬 완성!

int[] array = new int[n];
// 중략
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());

for (int i = end; i > start; i--) {
	for(int j = 0; j < i - start; j++) {
		temp = array[start + j];
		array[start + j] = array[start + j + 1];
		array[start + j + 1] = temp;
	}
}

• 내 풀이

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) {
		BufferedReader br;
		BufferedWriter bw;
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			bw = new BufferedWriter(new OutputStreamWriter(System.out));

			st = new StringTokenizer(br.readLine(), " ");
			int numOfBaskets = Integer.parseInt(st.nextToken());
			int numOfInput = Integer.parseInt(st.nextToken());

			int[] baskets = new int[numOfBaskets];
			for (int i = 0; i < numOfBaskets; i++) {
				baskets[i] = i + 1;
			}

			int start = 0;
			int end = 0;
			int temp = 0;
			int range = 0;

			for (int i = 0; i < numOfInput; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				start = Integer.parseInt(st.nextToken()) - 1;
				end = Integer.parseInt(st.nextToken()) - 1;

				if (end - start > 1) {
					if ((end - start) % 2 == 1) {
						range = (end - start) / 2 + 1;
					} else {
						range = (end - start) / 2;
					}
					for (int j = 0; j < range; j++) {
						temp = baskets[end - j];
						baskets[end - j] = baskets[start + j];
						baskets[start + j] = temp;
					}
				} else if (end - start == 1) {
					temp = baskets[end];
					baskets[end] = baskets[start];
					baskets[start] = temp;
				}

			}

			for (int i : baskets) {
				sb.append(i + " ");
			}

			bw.write(sb.toString());
			bw.flush();
			bw.close();
			br.close();

		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}